#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <math.h>
#include "err.h"
#include "ft_fifo.h"

/**
 * ft_fifo_init - allocates a new FIFO using a preallocated buffer
 * @buffer: the preallocated buffer to be used.
 * @size: the size of the internal buffer, this have to be a power of 2.
 * @lock: the lock to be used to protect the fifo buffer
 *
 * Do NOT pass the fifo to fifo_free() after use ! Simply free the
 * struct fifo with free().
 */
struct ft_fifo *ft_fifo_init(unsigned char *buffer, unsigned int size)
{
	struct ft_fifo *fifo;

	if(size & (size - 1)) {
		perror("fifo size error!\n");
		return ERR_PTR(-EINVAL);
	}

	fifo = malloc(sizeof(struct ft_fifo));
	if (!fifo) {
		perror("Malloc failed!(ft_fifo)\n");
		return ERR_PTR(-ENOMEM);
	}

	fifo->buffer = buffer;
	fifo->size = size;
	fifo->in = fifo->out = 0;

	if(pthread_mutex_init(&fifo->lock, NULL) != 0) {
		perror("Mutex initialization failed!\n");
		free(fifo);
		return ERR_PTR(-EPERM);
	}

	return fifo;
}

static __inline__ int fls(int x)
{
	int r = 32;

	if (!x)
		return 0;
	if (!(x & 0xffff0000u)) {
		x <<= 16;
		r -= 16;
	}
	if (!(x & 0xff000000u)) {
		x <<= 8;
		r -= 8;
	}
	if (!(x & 0xf0000000u)) {
		x <<= 4;
		r -= 4;
	}
	if (!(x & 0xc0000000u)) {
		x <<= 2;
		r -= 2;
	}
	if (!(x & 0x80000000u)) {
		x <<= 1;
		r -= 1;
	}
	return r;
}

static inline unsigned long roundup_pow_of_two(unsigned long x)
{
	return (1UL << fls(x - 1));
}

/**
 * ft_fifo_alloc - allocates a new FIFO and its internal buffer
 * @size: the size of the internal buffer to be allocated.
 * @lock: the lock to be used to protect the fifo buffer
 */
struct ft_fifo *ft_fifo_alloc(unsigned int size)
{
	unsigned char *buffer;
	struct ft_fifo *ret;

	if (size & (size - 1)) {
		size = roundup_pow_of_two(size);
	}

	buffer = malloc(size);
	if (!buffer)
		return ERR_PTR(-ENOMEM);


	ret = ft_fifo_init(buffer, size);

	if (IS_ERR(ret)) {
		free(buffer);
	}

	return ret;
}

/**
 * ft_fifo_free - frees the FIFO
 * @fifo: the fifo to be freed.
 */
void ft_fifo_free(struct ft_fifo *fifo)
{
	free(fifo->buffer);
	free(fifo);
}

/*
 * min()/max() macros that also do
 * strict type-checking.. See the
 * "unnecessary" pointer comparison.
 */
#define min(x,y) ({ \
	typeof(x) _x = (x);	\
	typeof(y) _y = (y);	\
	(void) (&_x == &_y);		\
	_x < _y ? _x : _y; })

#define max(x,y) ({ \
	typeof(x) _x = (x);	\
	typeof(y) _y = (y);	\
	(void) (&_x == &_y);		\
	_x > _y ? _x : _y; })


static inline int __ft_fifo_resize(struct ft_fifo *fifo)
{
	void *buf;
	unsigned int size;

	size = fifo->size << 1;
	
	buf = realloc(fifo->buffer, size);
	if(!buf) {
		return -1;
	}
	fifo->buffer = buf;
	fifo->size   = size;
	return 0;
}

/**
 * __ft_fifo_put - puts some data into the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: the data to be added.
 * @len: the length of the data to be added.
 *
 * This function copies at most 'len' bytes from the 'buffer' into
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __ft_fifo_put(struct ft_fifo *fifo,
			   unsigned char *buffer, unsigned int len)
{
	unsigned int l;

 reput:
	l = min(len, fifo->size - fifo->in + fifo->out);

	if(!l) {
		if(__ft_fifo_resize(fifo) < 0) {
			perror("fifo resize failed!\n");
			return 0;
		}
		goto reput;
	}

	/* first put the data starting from fifo->in to buffer end */
	l = min(l, fifo->size - (fifo->in & (fifo->size - 1)));
	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

	/* then put the rest (if any) at the beginning of the buffer */
	memcpy(fifo->buffer, buffer + l, len - l);

	fifo->in += len;

	return len;
}

/**
 * __ft_fifo_get - gets some data from the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: where the data must be copied.
 * @len: the size of the destination buffer.
 *
 * This function copies at most 'len' bytes from the FIFO into the
 * 'buffer' and returns the number of copied bytes.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __ft_fifo_get(struct ft_fifo *fifo,
			   unsigned char *buffer, unsigned int len)
{
	unsigned int l;

	len = min(len, fifo->in - fifo->out);

	/* first get the data from fifo->out until the end of the buffer */
	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

	/* then get the rest (if any) from the beginning of the buffer */
	memcpy(buffer + l, fifo->buffer, len - l);

	fifo->out += len;

	return len;
}
